package ljl.alg.jianzhioffer.round2;

import commons.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 力扣简单题，做过好几次了
 * 1. 放到 set 里，挨个判断
 * 2. 同时遍历两个 list，一个完了就去另一个，如果相交会相等
 * */
public class _52_intersection_node {
    
    public ListNode getIntersectionNode2(ListNode list1, ListNode list2) {
        ListNode p = list1, q = list2;
        while (p != q) {
            if (p == null) p = list2;
            else p = p.next;
            if (q == null) q = list1;
            else q = q.next;
        }
        return p;
    }
    
    public ListNode getIntersectionNode(ListNode a, ListNode b) {
        Set<ListNode> set = new HashSet<>();
        while (a != null) {
            set.add(a);
            a = a.next;
        }
        while (b != null) {
            if (set.contains(b)) return b;
            b = b.next;
        }
        return null;
    }
}
